IRA codes are, for example, described in the paper of Hui Jin et al entitled “Irregular Repeat-Accumulate Codes” presented at the second international conference on Turbo Codes, Brest, France, September 2000. Low-Density Parity-Check (LDPC) codes were introduced by Gallager in 1962 and rediscovered in 1996 by MacKay and Neal. For a long time they had no practical impact due to their computational and implementation complexity. This changed with advances in microelectronics that led to more computational power at hand for simulation and which now enables implementation. Due to their excellent error correction performance they are considered for future telecommunication standards.
An LDPC code is a linear block code defined by its sparse M×N parity check matrix H. It contains j ones per column and k ones per row, called row and column degree respectively. A (j,k)-regular LDPC code has row and column degree of uniform weight, otherwise the code is called irregular. A parity check code can be represented by a bipartite graph. The M check nodes correspond to the parity constraints, the N variable nodes represent the data symbols of the codeword. An edge in the graph corresponds to a one in the parity check matrix.
In the LDPC code encoder the packet to encode of size (N−M) is multiplied with a generator matrix G of size (N−M)×N. This multiplication leads to an encoded vector of length N. The generator matrix G and the parity check matrix H satisfy the relation GHt=0 where 0 is the null matrix.
Generally, an LDPC code decoder comprises a decoding module which receives the encoded vector of length N and delivers an intermediate vector of length N by using the parity check matrix H. Then a demapping module extracts the decoded vector of length (N−M) from the intermediate vector. More precisely, LDPC codes can be decoded using message passing algorithms, either in hard or soft decision form. The decoding is then an iterative process, which exchanges messages between variable and check nodes. Typically a Belief Propagation (BP) process is used, which exchanges soft-information iteratively between variable and check nodes. The code performance mainly depends on the randomness of the parity check matrix H, the codeword size N and the code rate R=(N−M)/N.
The channel coding part may be an important component in wireless communication systems like UMTS, WLAN and WPAN. Especially in the domain of WLAN and WPAN the latency of the decoding may be critical. Low Density Parity Check codes can be seen as a promising candidate for these systems in the near future. These codes are being deployed in the DVB-S2 standard and in some optical fiber communication systems. The codes have some interesting properties, which make them a natural choice for a latency critical application.
The new DVB-S2 standard features a powerful forward error correction (FEC) system, which allows for transmission close to the theoretical limit, i.e. provided by using LDPC codes, which can even outperform Turbo-Codes. To provide flexibility, 11 different code rates (R) ranging from R=¼ up to R= 9/10 are specified with a codeword length up to 64800 bits. This maximum codeword length is the reason for outstanding communication performance, so the codeword length of 64800 bits is described.
For the DVB-S2 code, 64800 so called variable nodes (VN) and 64800×(1−R) check nodes (CN) exist. The connectivity of these two types of nodes is specified in the standard. The variable nodes comprise information nodes and parity nodes. For decoding the LDPC code, messages are exchanged iteratively between these two types of nodes, while the node processing is of low complexity. Generally, within one iteration, first the variable nodes (VN) are processed (updated), then the check nodes (CN) are processed (updated) one after another. The problem of this conventional two phase-process or message passing, referred to as “two-phase MP”, is the slow convergence speed, i.e. the limited communications performance for a fixed number of iterations.
The Mansour et al. article entitled “High-Throughput LDPC Decoders”, IEEE Transactions on a Very Large Scale Integration Systems (VLSI), vol. 11, No. 6, pp 976-996, December 2003 has shown that the convergence speed can be improved when the updated messages of a node are directly passed to the other nodes. More precisely, according to this article, a subset of check nodes are processed separately and the newly calculated messages are immediately passed to the corresponding variable nodes. The variable nodes update their outgoing messages. The next check nodes subset will thus receive newly updated messages which improve convergence speed. This scheduling is called “Turbo Decoding Message Passing” in this article and referred to as “turbo MP” thereafter.
The Hocevar article entitled “A reduced complexity decoder architecture via layered decoding of LDPC codes”, in Proc. IEEE Workshop on Signal Processing Systems (SIPS '04), Austin, USA, October 2004, pp. 107-112, as well as the Colavolpe article entitled “Design and Performance of Turbo Gallager Codes”, IEEE Transactions on Communications, vol. 52, no. 11, pp. 1901-1908, November 2004, have teachings analogous to those of the Mansour et al. article.